`
https://leetcode.cn/problems/find-k-th-smallest-pair-distance/
`

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var smallestDistancePair = function (nums, k) {
  const n = nums.length
  nums.sort((a, b) => a - b)

  // 给定 x ，计算 nums 中数对距离 <= x 的个数 cnt，是否满足 cnt >= k
  const check = (x) => {
    let cnt = 0, i = 0
    for (let j = 0; j < n; j++) {
      while (nums[j] - nums[i] > x) i++
      cnt += j - i
      if (cnt >= k) return true
    }
    return false
  }

  let left = -1, right = nums.at(-1) - nums[0]
  while (left + 1 < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (check(mid)) {
      right = mid
    } else {
      left = mid
    }
  }
  return right
};